//超出内存限制
//dfs每块海洋（与陆地相邻），计算将其变成1后的陆地面积
//为了保证原来的不受影响，每次dfs都要拷贝一份
// class Solution {
//     int _n;

//     void dfs(vector<vector<int>>& grid, int m, int n, int& nums)
//     {
//         if (m < 0 || n < 0 || m >= _n || n >= _n || grid[m][n] != 1)
//         {
//             return;
//         }

//         grid[m][n] = 2;
//         nums++;
//         dfs(grid, m - 1, n, nums);    //上
//         dfs(grid, m, n - 1, nums);    //左
//         dfs(grid, m + 1, n, nums);    //下
//         dfs(grid, m, n + 1, nums);    //右
//     }
// public:
//     int largestIsland(vector<vector<int>>& grid) {
//         _n = grid.size();
//         int ret = 1;

//         for (int i = 0; i < _n; i++)
//             for (int j = 0; j < _n; j++)
//                 if (grid[i][j] == 0 &&
//                    (i > 0 && grid[i - 1][j] == 1 || 
//                     i < _n - 1 && grid[i + 1][j] == 1 ||
//                     j > 0 && grid[i][j - 1] == 1 ||
//                     j < _n - 1 && grid[i][j + 1] == 1 ))
//                 {
//                     int nums = 0;
//                     vector<vector<int>> tmp = grid;
//                     tmp[i][j] = 1;
//                     dfs(tmp, i, j, nums);
//                     ret = max(ret, nums);
//                     tmp[i][j] = 0;
//                 }
//         if (grid[0][0])
//         {
//             int nums = 0;
//             dfs(grid, 0, 0, nums);
//             ret = max(ret, nums);
//         }

//         return ret;
//     }
// };

//换一种思路
//求得每个岛屿的面积后，再遍历每块海洋
    //将遍历到的海洋填为陆地，并查找相邻的陆地面积，进行面积相加，求最大值
//考虑到一块海洋可能被同一块陆地多次相邻的情况，需要对每一块陆地作标记
//用一个数组存储每块岛屿的面积，同时不同岛屿的陆地用自己面积对应的下标进行标记
//  为了防止和0/1重复，规定 下标 = 标记 - 2
class Solution {
    int board;
    vector<int> g_size;

    void dfs(vector<vector<int>>& grid, int m, int n, int& nums, int flag)
    {
        if (m < 0 || n < 0 || m >= board || n >= board || grid[m][n] != 1)
            return;

        grid[m][n] = flag;
        nums++;
        dfs(grid, m - 1, n, nums, flag);    //上
        dfs(grid, m, n - 1, nums, flag);    //左
        dfs(grid, m + 1, n, nums, flag);    //下
        dfs(grid, m, n + 1, nums, flag);    //右
    }

public:
    int largestIsland(vector<vector<int>>& grid) {
        board = grid.size();
        int ret = 0;
        int flag = 2;  // 从2开始标记岛屿，避免与0和1冲突

        // 第一步：计算每个岛屿的面积，并标记岛屿
        for (int i = 0; i < board; i++) {
            for (int j = 0; j < board; j++) {
                if (grid[i][j] == 1) {
                    int nums = 0;
                    dfs(grid, i, j, nums, flag);
                    g_size.push_back(nums);
                    ret = max(ret, nums);  // 更新最大岛屿面积
                    flag++;
                }
            }
        }

        // 第二步：遍历所有海洋格子，计算填海后的最大岛屿面积
        for (int i = 0; i < board; i++) {
            for (int j = 0; j < board; j++) {
                if (grid[i][j] == 0) {
                    unordered_set<int> neighborIslands;  // 用于存储相邻的岛屿标识符
                    int area = 1;  // 当前海洋格子变成陆地后的面积

                    // 检查上下左右的相邻格子
                    if (i > 0 && grid[i - 1][j] >= 2) {
                        neighborIslands.insert(grid[i - 1][j]);
                    }
                    if (i < board - 1 && grid[i + 1][j] >= 2) {
                        neighborIslands.insert(grid[i + 1][j]);
                    }
                    if (j > 0 && grid[i][j - 1] >= 2) {
                        neighborIslands.insert(grid[i][j - 1]);
                    }
                    if (j < board - 1 && grid[i][j + 1] >= 2) {
                        neighborIslands.insert(grid[i][j + 1]);
                    }

                    // 将相邻的岛屿面积相加
                    for (int island : neighborIslands) {
                        area += g_size[island - 2];  // 减去2得到正确的索引
                    }

                    ret = max(ret, area);  // 更新最大岛屿面积
                }
            }
        }

        return ret;
    }
};